Automat

Limit pamięci: 128 MB

W budynku uczelni, na której studiuje Bajtazar, stoi automat sprzedający batony. W automacie dostępnych jest rodzajów batonów, ponumerowanych od do . Batony poszczególnych rodzajów różnią się rozmiarem oraz smakiem, więc ich ceny mogą być różne.

Niedawno Bajtazar odkrył, że automat jest popsuty. Kiedy kupi się jednego batona rodzaju , z automatu wypada także po jednym batonie każdego z rodzajów , , ..., . Oczywiście tylko wtedy, gdy batony tych rodzajów są dostępne - jeśli batonów któregoś rodzaju między a nie ma w automacie, baton tego rodzaju nie wypada. Trzeba dodać, że ta sprytna sztuczka jest możliwa do wykonania tylko wtedy, gdy w automacie faktycznie znajduje się co najmniej jeden baton -tego rodzaju.

Bajtazar postanowił zrobić użytek z wykrytej usterki. Dysponując pewną kwotą pieniędzy, chciałby stwierdzić, jaką największą wartość (tj. sumę cen) łakoci może wydobyć z automatu za tę kwotę. Bajtazar nie musi zużyć całej dostępnej kwoty.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz (, ), oznaczające liczbę rodzajów batonów w automacie oraz kwotę, jaką dysponuje Bajtazar. Drugi wiersz zawiera liczb całkowitych (), oznaczających ceny batonów poszczególnych rodzajów. Trzeci wiersz zawiera liczb całkowitych (), oznaczających liczby batonów poszczególnych rodzajów dostępnych w automacie.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą - sumę cen łakoci, jakie Bajtazar może nabyć w automacie, dysponując kwotą .

Przykład

Dla danych wejściowych:

6 8
7 2 3 5 7 2
1 3 0 3 2 1

poprawną odpowiedzią jest:

30

Wyjaśnienie do przykładu: Kupujemy batona rodzaju 6, a z automatu wypada nam także po jednym batonie rodzajów 1, 2, 4 i 5. Kupujemy batona rodzaju 4, z automatu oprócz niego wypada baton rodzaju 2.

Autor zadania: Jakub Pachocki.